"""
1.预处理优化：
    使用三个二维数组rows/cols/boxes预先记录每个位置已使用的数字
    有效性检查时间复杂度从O(n)降至O(1)（直接数组查询代替遍历检查）
2.空格预收集：
    预先收集所有空格位置到spaces列表
    避免每次递归都遍历整个数独板查找空格
3.候选排序优化：
    对候选数字按升序排列（'1'到'9'顺序）
    优先尝试小数字可能更快找到解，减少回溯次数
4.内存优化：
    使用布尔数组替代集合操作，减少内存占用
    避免在递归中创建临时数据结构
5.剪枝优化：
    当所有空格填满时立即返回（idx == len(spaces)）
    减少不必要的递归调用
"""

class Solution:
    def solveSudoku(self, board: list[list[str]]) -> None:
        # 预处理行、列、子网格的已用数字
        self.rows = [[False] * 10 for _ in range(9)]
        self.cols = [[False] * 10 for _ in range(9)]
        self.boxes = [[[False] * 10 for _ in range(3)] for _ in range(3)]
        self.spaces = []  # 存储所有空格坐标

        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    num = int(board[i][j])
                    self.rows[i][num] = True
                    self.cols[j][num] = True
                    self.boxes[i // 3][j // 3][num] = True
                else:
                    self.spaces.append((i, j))

        self.backtrack(board, 0)

    def backtrack(self, board: list[list[str]], idx: int) -> bool:
        if idx == len(self.spaces):
            return True  # 所有空格填满，找到解

        i, j = self.spaces[idx]

        # 生成候选数字并按升序排列（启发式优化）
        candidates = []
        for k in '123456789':
            num = int(k)
            if not (self.rows[i][num] or self.cols[j][num] or self.boxes[i // 3][j // 3][num]):
                candidates.append(k)

        # 尝试所有候选数字
        for k in candidates:
            num = int(k)
            # 更新预处理数据
            self.rows[i][num] = self.cols[j][num] = self.boxes[i // 3][j // 3][num] = True
            board[i][j] = k
            # 递归
            if self.backtrack(board, idx + 1):
                # 结果为真，结束这一个，去尝试下一个
                return True
            # 当前 结果为假，回溯，恢复到上一步
            # 回溯操作
            self.rows[i][num] = self.cols[j][num] = self.boxes[i // 3][j // 3][num] = False
            board[i][j] = '.'

        return False